use std::sync::Arc;
use tokio::sync::Mutex;
use futures::future::{BoxFuture, FutureExt};

#[derive(Clone)]
struct Graph {
    nodes: Vec<usize>,
    edges: Vec<Vec<usize>>,
}

impl Graph {
    fn new(size: usize) -> Self {
        let mut edges = vec![vec![]; size];
        for i in 0..size-1 {
            edges[i].push(i+1);
        }
        Self { 
            nodes: (0..size).collect(), 
            edges 
        }
    }
}

async fn process_graph(graph: Arc<Graph>) -> Vec<usize> {
    let visited = Arc::new(Mutex::new(vec![false; graph.nodes.len()]));
    let result = Arc::new(Mutex::new(Vec::new()));
    
    fn bfs(
        graph: Arc<Graph>,
        node: usize,
        visited: Arc<Mutex<Vec<bool>>>,
        result: Arc<Mutex<Vec<usize>>>,
    ) -> BoxFuture<'static, ()> {
        async move {
            let mut v_lock = visited.lock().await;
            if v_lock[node] {
                return;
            }
            v_lock[node] = true;
            drop(v_lock);
            
            let mut r_lock = result.lock().await;
            r_lock.push(node);
            drop(r_lock);
            
            let mut handles = vec![];
            for &neighbor in &graph.edges[node] {
                handles.push(tokio::spawn(bfs(
                    graph.clone(),
                    neighbor,
                    visited.clone(),
                    result.clone()
                )));
            }
            
            for handle in handles {
                handle.await.unwrap();
            }
        }.boxed()
    }

    let root = 0;
    bfs(graph, root, visited, result.clone()).await;
    Arc::try_unwrap(result).unwrap().into_inner()
}

#[tokio::test]
async fn test_async_graph() {
    let graph = Arc::new(Graph::new(5));
    let nodes = process_graph(graph).await;
    assert_eq!(nodes, vec![0, 1, 2, 3, 4]);
}

#[tokio::main]
async fn main() {
    let graph = Arc::new(Graph::new(10));
    let result = process_graph(graph).await;
    println!("Traversal path: {:?}", result);
}